package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 二进制求和
        class Solution {
            public String addBinary(String a, String b) {
                int i = a.length() - 1, j = b.length() - 1;
                int carry = 0;
                // 预估容量：最大长度 + 1（可能多出一个进位）
                StringBuilder sb = new StringBuilder(Math.max(a.length(), b.length()) + 1);

                while (i >= 0 || j >= 0 || carry != 0) {
                    int sum = carry;
                    if (i >= 0) sum += a.charAt(i--) - '0';
                    if (j >= 0) sum += b.charAt(j--) - '0';

                    sb.append(sum % 2);   // 当前位
                    carry = sum / 2;      // 新进位
                }

                return sb.reverse().toString();
            }
        }

        // 字符串相乘
        class Solution2 {
            public String multiply(String num1, String num2) {
                // 1) 边界：任一为 "0"
                if (num1.equals("0") || num2.equals("0")) return "0";

                int m = num1.length(), n = num2.length();
                char[] a = new StringBuilder(num1).reverse().toString().toCharArray();
                char[] b = new StringBuilder(num2).reverse().toString().toCharArray();

                // 2) 无进位卷积：长度 m + n - 1
                int[] tmp = new int[m + n - 1];
                for (int i = 0; i < m; i++) {
                    int di = a[i] - '0';
                    for (int j = 0; j < n; j++) {
                        int dj = b[j] - '0';
                        tmp[i + j] += di * dj; // 累加！！不是覆盖
                    }
                }

                // 3) 统一进位：从低到高，把每格拆成 个位(输出) + 进位(带走)
                StringBuilder sb = new StringBuilder(m + n);
                int cur = 0, carry = 0;
                while (cur < tmp.length || carry != 0) {
                    if (cur < tmp.length) carry += tmp[cur++];
                    sb.append((char) ('0' + (carry % 10)));
                    carry /= 10;
                }

                // 4) 去掉将来会成为“前导零”的尾部 0（至少保留1位）
                while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
                    sb.deleteCharAt(sb.length() - 1);
                }

                // 5) 反转得到正常顺序
                return sb.reverse().toString();
            }
        }

    }
}